1. Field of the Invention
This invention relates to means and methods of processing optical image edge data by approximating a quadratic function by a linear function and by approximating coefficients in the linear function.
2. Prior Art
FIG. 1 shows a partial schematic of imaging screen 10 with an actual image edge line 12 superimposed thereupon. Twelve pixels numbered 14 through 36 are shown on screen 10 in FIG. 1. For illustrative purposes, the area 38 to the upper left of line 12, which includes pixels 14, 16 and 22, is chosen to be a light area and the area 40 to the lower right of line 12 including the remainder of the twelve pixels is chosen to be a dark area. Other pixels (not shown) would cover the remainder of screen 10 to complete an orthogonal grid pattern.
The pixels in light area 38 could all be of a first uniform intensity or could have varying intensities as could the pixels included in the dark area 40, but all pixels in light area 38 will have a higher intensity than any pixel in dark area 40. TV screens generally display data in analog form, however data extracted from the light intensities of pixels on the screen such as screen 10 are generally converted to digital signals for image processing purposes.
A well known method of processing pixel intensity data to determine the location of edge line 12 or to enhance images is to employ the Sobel square root magnitude expression given by: ##EQU1## where Si is the magnitude of the Sobel square root edge operator for a point i,
Xsi is the horizontal edge component of S along the x-axis for point i and Ysi is the vertical edge component of PA1 S along the y-axis for point i where the x and y axes are mutually orthogonal.
Xs and Ys are determined for each pixel (i.e., for each point i) on screen 10 by spatially processing the discrete image array F(j,k) of nine pixels centered about the pixel of interest, where j and k designate array elements. For example, the discrete image array for pixel 24 includes pixels 14, 16, 18, 22, 24, 26, 30, 32 and 34. For edge pixels such as pixel 14, the nine elements for the discrete array would include pixels 14, 16, 22 and 24 and various values would be assumed for pixels which would be located off screen.
For each pixel two gradient functions Xs=Gl(j,k) and Ys=G2(j,k) are generated by: EQU G.sub.1,2 (j,k)=F.sub.i (j,k) .circle.X H.sub.1,2 (j,k) (2)
where .circle.X denotes two dimensional spatial convolution and H1 and H2 are linear operators given by ##EQU2## From FIG. 1 it can be seen that for pixel 24 (the ith point in this example) orthogonal components Xsi and Ysi of the Sobel square root edge operator define the direction and magnitude of S. Equation 1 generates the magnitude of S and the orientation of S (see .theta. in FIG. 1) is given by: ##EQU3##
Equations 1 and 5 will yield only approximations of the edge magnitude and orientation of edge 12. The true magnitude of S at point 42 is illustrated as S* in FIG. 1 and the true orientation of S* is given by .phi. in FIG. 1.
FIG. 2 illustrates edge gradient amplitude response as a function of actual edge orientation for the Sobel operator. Note that the Sobel square root amplitude response is relatively invariant to actual orientation but is consistently high over much of the 0 to .pi./4 range by about 10%.
FIG. 3 indicates that the Sobel operator provides very linear response between the actual and the detected edge orientation.
Two other common square root edge operators are the Prewitt and Roberts square root operators. Equations 1 and 2 are valid for these operators as well, however matrixes H.sub.1 and H.sub.2 are different for each operator.
Further discussions of the Sobel operator and other spatial edge enhancement operators are found in I. E. Abdou and W. K. Pratt "Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors", U.S.C. Semiannual Technical Report, Vol. 840, pages 28 to 46, September, 1978, and R. A. Duda and P. E. Hart, Pattern Classification and Scene Analysis, Wiley, N.Y., 1973, the same being incorporated herein by reference.
S could be calculated from equation 1 by using a look-up table approach wherein various values of Xs and Ys as well as the square root of the sum of these squared quantities would be available for the range of possible Xs and Ys. Such information could, for example, be held in a semiconductor ROM. However, implementation of such an approach with a ROM requires random logic to implement adders necessary for generating the sum in equation 1 which in turn necessitates custom semiconductor chip development. Further, as larger bit input data is used to increase or insure the accuracy of S, the size of the ROM is substantially increased. Also, the method of the present invention can be implemented on a single commercial gate array chip with virtually no memory or memory control requirements.
Techniques where S could be accurately approximated while substantially avoiding the look-up approach would facilitate processing of edge data by both substantially increasing speed (by avoiding memory access) and reducing hardware requirements.